package 回溯法.BFS;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-20
 */
public class 打开转盘锁 {
    public static void main(String[] args) {

//        System.out.println(openLockDouble(new String[]{"0101"}, "0909"));
        System.out.println(openLock(new String[]{"0101"}, "0909"));
//        System.out.println(openLockDfs("01000", "09000"));
    }

  static   boolean[] visited = new boolean[100000];
    static AtomicInteger  atomicInteger = new AtomicInteger(1);
    public static int openLockDfs(String current, String target) {
        int total = 0;
        visited[Integer.parseInt(current)] = true;
        if (current == target) {

            return 0;
        }
        System.out.println(atomicInteger.getAndIncrement());

        for (int i = 0; i < current.length(); i++) {
            String minus = minusOne(current, i);
            String plus = plusOne(current, i);
            int i1 = Integer.parseInt(target);
            int i2 = Integer.parseInt(minus);
            int i3 = Integer.parseInt(plus);
            int left=0, right = 0;
            if (!visited[Integer.parseInt(plus)]) {
                visited[Integer.parseInt(plus)] = true;
                left += openLockDfs(plus, target) + 1;
            }
            if (!visited[Integer.parseInt(minus)]) {
                visited[Integer.parseInt(minus)] = true;
                right +=  openLockDfs(minus, target) + 1;
            }
            total = Math.min(left, right);
        }
        return total;
    }

    public static int openLock(String[] deadEnds, String target) {
        Set<String> visited = new HashSet<>(Arrays.asList(deadEnds));
        Queue<String> queue = new ArrayDeque<>();
        List<String> path = new ArrayList<>();
        queue.offer("0000");
        visited.add("0000");
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                String cur = queue.poll();
                path.add(cur + ">");
                if (target.equals(cur)) {
                    return step;
                }
                for (int i = 0; i < cur.length(); i++) {
                    String plus = plusOne(cur, i);
                    if (!visited.contains(plus)) {
                        queue.offer(plus);
                        visited.add(plus);
                    }
                    String minus = minusOne(cur, i);
                    if (!visited.contains(minus)) {
                        queue.offer(minus);
                        visited.add(minus);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    //双向 BFS 也有局限，因为你必须知道终点在哪⾥。⽐如我们刚才讨 论的⼆叉树最⼩⾼度的问题，
    // 你⼀开始根本就不知道终点在哪⾥，也就⽆法 使⽤双向 BFS；
    // 但是第⼆个密码锁的问题，是可以使⽤双向 BFS 算法来提 ⾼效率的，代码稍加修改即可：
    public static int openLockDouble(String[] deadEnds, String target) {
        Set<String> visited = new HashSet<>(Arrays.asList(deadEnds));
        List<String> path = new ArrayList<>();
        Set<String> q1 = new HashSet<>();
        Set<String> q2 = new HashSet<>();
        q1.add("0000");
        q2.add(target);
        int step = 1;
        while ((!q1.isEmpty() && !q2.isEmpty())) {
            Set<String> temp = new HashSet<>(); /* 将 q1 中的所有节点向周围扩散 */
            if (q1.size() > q2.size()) { // 交换 q1 和 q2
                temp = q1;
                q1 = q2;
                q2 = temp;
            }
            for (String cur : q1) { /* 判断是否到达终点 */
                if (visited.contains(cur)) continue;
                if (q2.contains(cur)) return step;
                visited.add(cur); /* 将⼀个节点的未遍历相邻节点加⼊集合 */
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) temp.add(up);
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) temp.add(down);
                }
            }
            /* 在这⾥增加步数 */
            step++;
            // temp 相当于 q1
            // 这⾥交换 q1 q2，下⼀轮 while 就是扩散q2
            q1 = q2;
            q2 = temp;
        }
        return -1;
    }

    //转盘往上拨
    public static String plusOne(String s, int j) {
        char[] chars = s.toCharArray();
        if (chars[j] == '9') {
            chars[j] = '0';
        } else {
            chars[j] += 1;
        }
        return new String(chars);
    }

    //转盘往下拨
    public static String minusOne(String s, int j) {
        char[] chars = s.toCharArray();
        if (chars[j] == '0') {
            chars[j] = '9';
        } else {
            chars[j] -= 1;
        }
        return new String(chars);
    }
}
